package Demo01;

import java.util.Arrays;
import java.util.Stack;

import static com.sun.deploy.net.MessageHeader.merge;

public class Sort {
    private static void swap(int i, int j, int[] arr) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void InsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
        /*if(arr.length<=1) {
            return;
        }
        int count = 1;
        while (count<=arr.length-1) {
            int i = count;
            int tmp = arr[i];
            while(i>0) {
                if(arr[i-1]>tmp) {
                    arr[i] = arr[i-1];
                }else {
                    break;
                }
                i--;
            }
            arr[i] = tmp;
            count++;
        }*/
    }

    public static void ShellSort(int[] arr) {
        int gap = arr.length;
        while(gap>1) {
            gap /= 2;
            Shell(arr,gap);
        }
    }

    /**
     * 对每组进行插入排序
     * @param arr
     * @param gap
     */
    private static void Shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(arr[j]>tmp) {
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public static void selectSort(int[] arr) {
        if(arr.length<=1) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(minIndex,i,arr);
        }
    }
    public static void selectSort2(int[] arr) {
        if(arr.length<=1) {
            return;
        }
        int left = 0;
        int right = arr.length-1;
        while (left<right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if(arr[minIndex]>arr[i]) {
                    minIndex = i;
                }
                if(arr[maxIndex]<arr[i]) {
                    maxIndex = i;
                }
            }
            swap(minIndex,left,arr);
            if(left==maxIndex) {
                maxIndex = minIndex;
            }
            swap(maxIndex,right,arr);
            left++;
            right--;
        }
    }
    static void heapSort(int[] arr) {
        createHeap(arr);
        int end = arr.length-1;
        while (end!=0) {
            swap(end,0,arr);
            adjustDown(arr,0,end);
            end--;
        }
    }

    private static void createHeap(int[] arr) {
        for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            adjustDown(arr,parent,arr.length);
        }
    }

    private static void adjustDown(int[] arr, int parent, int length) {
        int child = parent*2+1;
        while (child<length) {
            if(child+1<length&&arr[child+1]>arr[child]) {
                child++;
            }
            if(arr[child]>arr[parent]) {
                swap(child,parent,arr);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        //i表示趟数
        //flg表示判断这一趟是否交换,没交换的话说明已经排序好了
        for (int i = 0; i < arr.length-1; i++) {
            boolean flg = true;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]) {
                    swap(j,j+1,arr);
                    flg = false;
                }
            }
            if(flg) {
                break;
            }
        }
    }
    public static void InsertSort(int[] arr, int start, int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= start; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    private static int part(int[] arr, int left, int right) {
        int std = arr[left];
        int start = left;
        while (left!=right) {
            while (left<right&&arr[right]>=std) {
                right--;
            }
            while (left<right&&arr[left]<=std) {
                left++;
            }
            swap(right,left,arr);
        }
        swap(start,left,arr);
        return left;
    }
    public static void quickSortRor(int[] arr) {
        int start = 0;
        int end = arr.length-1;
        Stack<Integer> stack = new Stack<>();
        int std = DigHole(arr,start,end);
        if(std-1>start) {
            stack.push(start);
            stack.push(std-1);
        }
        if(std+1<end) {
            stack.push(std+1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            if(!stack.isEmpty()) {
                end = stack.pop();
                start = stack.pop();
            }
            std = DigHole(arr,start,end);
            if(std-1>start) {
                stack.push(start);
                stack.push(std-1);
            }
            if(std+1<end) {
                stack.push(std+1);
                stack.push(end);
            }
        }

    }
    private static void quick(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        if(right-left<=10) {
            InsertSort(arr,left,right);
            return;
        }
        int mid = middleNum(arr,left,right);
        swap(mid,left,arr);

        int res = part(arr,left,right);
        quick(arr,left,res-1);
        quick(arr,res+1,right);
    }
    private static int DigHole(int[] arr, int left, int right) {
        int std = arr[left];
        int start = left;
        while (left<right) {
            while (left<right&&arr[right]>=std) {
                right--;
            }
            arr[left] = arr[right];
            while (left<right&&arr[left]<=std) {
                left++;
            }
            arr[right] = arr[left];

        }
        arr[left] = std;
        return left;
    }

    private static int middleNum(int[] arr, int left, int right) {
        int mid = (left+right)/2;
        if(arr[left]<arr[right]) {
            if(arr[mid]<arr[left]) {
                return left;
            } else if (arr[right]>arr[mid]) {
                return right;
            } else {
                return mid;
            }
        }else {
            if(arr[mid]<arr[right]) {
                return right;
            } else if (arr[left]>arr[mid]) {
                return left;
            } else {
                return mid;
            }
        }
    }
    public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while (gap<arr.length) {
            for (int i = 0; i < arr.length; i+=gap*2) {
                int left = i;
                int mid = left+gap-1;
                int right = mid+gap;
                if(mid>=arr.length) {
                    mid = arr.length-1;
                }
                if(right>=arr.length) {
                    right = arr.length - 1;
                }
                merge(arr,left,mid,right);
            }

            gap *= 2;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int oneStart = left;
        int oneEnd = mid;
        int twoStart = mid+1;
        int twoEnd = right;
        int[] tmpArray = new int[right-left+1];
        int k = 0;
        while (oneStart<=oneEnd&&twoStart<=twoEnd) {
            if(arr[oneStart]<arr[twoStart]) {
                tmpArray[k++] = arr[oneStart++];
            }else {
                tmpArray[k++] = arr[twoStart++];
            }
        }
        while(oneStart<=oneEnd) {
            tmpArray[k++] = arr[oneStart++];
        }
        while (twoStart<=twoEnd) {
            tmpArray[k++] = arr[twoStart++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            arr[i+left] = tmpArray[i];
        }
    }
    public static void mergeSort(int[] arr) {
        mergeLink(arr,0,arr.length-1);
    }



    private static void mergeLink(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        int mid = (left+right)/2;
        mergeLink(arr,left,mid);
        mergeLink(arr,mid+1,right);
        merge(arr,left,mid,right);
    }



    private static int leftrRightPointers(int[] arr, int left, int right) {
        int prev = left;
        int cur = left+1;
        while (cur<=right) {
            if(arr[cur]<arr[left]&&arr[++prev]!=arr[cur]) {
                swap(cur,prev,arr);
            }
            cur++;
        }
        swap(prev,left,arr);
        return prev;
    }
    public static void countSort(int[] arr) {
        if(arr.length<=1) {
            return;
        }
        //求最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max) {
                max = arr[i];
            }
            if(arr[i]<min) {
                min = arr[i];
            }
        }
        //确定数组长度
        int[] countArray = new int[max-min+1];
        //遍历数组,把数据出现的次数存储到数组中
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i]-min]++;
        }
        //遍历计数数组 把实际的数据写回arr数组
        int k = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i]>0) {
                arr[k++] = i+min;
                countArray[i]--;
            }
        }
    }
}


 /*public static void mergeSort(int[] arr) {
        mergeSortFun(arr,0,arr.length-1);
    }

    private static void mergeSortFun(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        int mid = (left+right)/2;
        mergeSortFun(arr,left,mid);
        mergeSortFun(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmpArray = Arrays.copyOf(arr,right-left+1);
        int k = 0;
        int oneStart = left;
        int oneEnd = mid;
        int twoStart = mid+1;
        int twoEnd = right;
        while (oneStart<=oneEnd&&twoStart<=twoEnd) {
            if(arr[oneStart]<arr[twoStart]) {
                tmpArray[k++] = arr[oneStart++];
            }else {
                tmpArray[k++] = arr[twoStart++];
            }
        }
        while (oneStart<=oneEnd) {
            tmpArray[k++] = arr[oneStart++];
        }
        while (twoStart<=twoEnd) {
            tmpArray[k++] = arr[twoStart++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            arr[i+left] = tmpArray[i];
        }
    }*/

/*private static void createHeap(int[] arr) {
        for (int i = (arr.length-1-1)/2; i >= 0; i--) {
            abjustDown(arr,i,arr.length);
        }
    }
    public static void heapSort(int[] arr) {
        createHeap(arr);
        int end = arr.length-1;
        while (end!=0) {
            swap(0,end,arr);
            abjustDown(arr,0,end);
            end--;
        }
    }
    private static void abjustDown(int[] arr, int index, int length ) {
        int parent = index;
        int child =parent*2+1;
        while (child<length) {
            if(child+1<length&&arr[child+1]>arr[child]) {
                child++;
            }
            if(arr[child]>arr[parent]) {
                swap(child,parent,arr);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }

        }
    }*/